package com.example.hot100;

import com.example.tree.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。
 *  有效 二叉搜索树定义如下：
 *  节点的左子树只包含 小于 当前节点的数。
 *  节点的右子树只包含 大于 当前节点的数。
 *  所有左子树和右子树自身必须也是二叉搜索树。
 *
 *  示例 1：
 * 输入：root = [2,1,3]
 * 输出：true
 *
 *  示例 2：
 * 输入：root = [5,1,4,null,null,3,6]
 * 输出：false
 * 解释：根节点的值是 5 ，但是右子节点的值是 4 。
 */
public class Leetcode98_IsValidBST {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(2);
        root.left = new TreeNode(1);
        root.right = new TreeNode(3);
        System.out.println(new Solution().isValidBST(root));
    }

    static class Solution {
        /**
         * 中序遍历(迭代实现)
         * 因为二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，
         * 所以在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可
         *
         * @param root
         * @return
         */
        public boolean isValidBST3(TreeNode root) {
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode tmp = root;
            long pre = Long.MIN_VALUE;// 用于记录上一个中序遍历的值
            while (!stack.isEmpty() || tmp != null) {
                while (tmp != null) {
                    stack.push(tmp);
                    tmp = tmp.left;
                }

                tmp = stack.pop();
                if (tmp.val <= pre) return false;
                pre = tmp.val;

                tmp = tmp.right;
            }

            return true;

        }

        /**
         * 中序遍历(递归方式)
         * @param root
         * @return
         */
        public boolean isValidBST2(TreeNode root) {
            return inOrder(root);

        }

        /**
         * 递归方式
         * @param root
         * @return
         */
        public boolean isValidBST1(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);

        }

        public boolean isValidBST(TreeNode root) {
            return isValidBST1(root);

        }

        public boolean isValidBST(TreeNode root, long lower, long upper) {
            if (root == null) return true;

            if (root.val <= lower || root.val >= upper) return false;
            return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);

        }

        private long pre = Long.MIN_VALUE;// 用于记录上一个中序遍历的值
        private boolean inOrder(TreeNode root) {
            if (root == null) return true;
            boolean leftRes = inOrder(root.left);
            if (pre >= root.val) return false;
            pre = root.val;
            boolean rightRes = inOrder(root.right);
            return leftRes && rightRes;
        }
    }
}
